In computer graphics, triangular meshes are widely used to render realistic 3D images. A realistic 3D image represented by a triangular mesh includes vertices information on vertices of triangles in the mesh and connectivity information on connectivity between vertices, and hence has a much larger amount of data compared to a regular 2D image.
Accordingly, research efforts have been continuously made to solve the problems in storage and transmission of 3D images represented by triangular meshes.
Although 3D graphics is in demand recently, its use is limited because of vast amount of data being required.
For example, when vertices information of a 3D mesh model is represented using 32-bit floating-point numbers, representing a single vertex requires 96 bits (12 bytes) of memory.
Therefore, a 3D mesh model having 10,000 vertices as vertices information will require 120 KB of storage, and a 3D mesh model having 100,000 vertices will require 1.2 MB of storage.
Further, connectivity information may include repeated vertex references, requiring a significant amount of storage.
To cope with the requirement of the huge amount of data, coding schemes for compressing 3D images have been developed. For example, a 3D mesh coding (3DMC) scheme is adopted in virtual reality modeling language (VRML) and the MPEG-4 ISO/IEC standard. Particularly, in the MPEG-4 standard, the 3DMC scheme provides a compression tool for an IndexedFaceSet node representing a 3D model in a VRML file, and enables compression and decompression of the geometry and connectivity information of the 3D model to thereby increase efficiency of transmission of 3D mesh information.
FIG. 1 is a block diagram of an existing 3DMC encoder 110.
Referring to FIG. 1, the existing 3DMC encoder 110 includes a topological surgery module 111 decomposing a 3D mesh model being source data having vertex, connectivity and property information into 2D meshes, a vertex information encoding module 112, a connectivity information encoding module 113, a property information encoding module 114, and an entropy encoding module 115 compressing the results encoded by the vertex information encoding module 112, connectivity information encoding module 113 and property information encoding module 114 into a 3DMC bitstream.
In the 3DMC encoder 110, the main feature of 3DMC a topological surgery performed by the topological surgery module 111 to obtain a high compression ratio. In topological surgery, a triangular mesh of a 3D model is assumed to be homeomorphic to a sphere, and is converted into a 2D mesh structure by cutting the triangular mesh along the cutting edges.
FIG. 2 is a block diagram of a 3DMC decoder 210 corresponding to the 3DMC encoder 110 of FIG. 1.
Referring to FIG. 2, the 3DMC decoder 210 includes an entropy information decoding module 211, vertex information decoding module 212, connectivity information decoding module 213, property information decoding module 214, and topological synthesis module 215, and restores the original 3D model data from a 3DMC bitstream.
FIG. 3 illustrates an overall structure of a bitstream representing mesh information of a 3D model produced by the encoder of FIG. 1.
Referring to FIG. 3, a bitstream representing encoded mesh information of a 3D model includes a triangle tree 303 related to a binary triangle spanning tree composed of triangular strips, a vertex graph 301 indicating edges between vertices cutting the 3D mesh, and triangle data 305 related to data values of the 3D mesh.
FIGS. 4 to 7 illustrate steps involved in topological surgery of a 3D mesh model.
A 3D mesh model shown in FIG. 4 is cut along the cut edges (marked in thick lines), resulting in a triangle tree shown in FIG. 5.
For fast processing of graphics data, objects are generally modeled in units of triangles, and triangles are preferably connected together to form a strip or fan rather than an arbitrary pattern. Repeated symbols in graphics data result in a high compression ratio. In conventional topological surgery, a 3D mesh model is cut along the cut edges into a triangle tree as shown in FIG. 5.
Next, a reference point is selected from the triangle tree, and a link is made between the selected reference point and the outermost vertex of a branching triangle, resulting in a vertex graph as shown in FIG. 6.
Then, a bounding loop is formed using the vertex graph, as shown in FIG. 7.
As described above, in the MPEG-4 3DMC scheme, compression of a 3D model represented by an IndexedFaceSet node involves the process of topological surgery to decompose the mesh structure of the 3D model into a 2D mesh map structure.
Although, representing a 3D mesh structure by a vertex graph and triangle tree enables achievement of a high compression ratio for a 3D model, which may cause a problem of changing original vertex position information of the 3D model.
That is, for further compression after topological surgery, the existing 3DMC encoder sends a newly indexed version of the vertex position information of the 3D model to the 3DMC decoder.
Consequently, the 3DMC decoder may be unaware of the original vertex position information of the 3D model so that an animation application requiring information on the order of vertices may be not supported.
In addition, whereas topological surgery, decomposing the connectivity information of a 3D mesh into a 2D mesh map, triangle tree and vertex graph, is effective for achievement of a high compression ratio, but it involves complex operations consuming most of the time and resources needed in compression.